package com.kobe.game_40;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.LinkedList;
import java.util.List;

import com.kobe.util.Prime;

/**
 * 
 * Consider all integer combinations of a^(b) for 2 ≤ a ≤ 5 and 2 ≤ b ≤ 5:
 * 
 * 2^(2)=4, 2^(3)=8, 2^(4)=16, 2^(5)=32 3^(2)=9, 3^(3)=27, 3^(4)=81, 3^(5)=243
 * 4^(2)=16, 4^(3)=64, 4^(4)=256, 4^(5)=1024 5^(2)=25, 5^(3)=125, 5^(4)=625,
 * 5^(5)=3125
 * 
 * If they are then placed in numerical order, with any repeats removed, we get
 * the following sequence of 15 distinct terms:
 * 
 * 4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125
 * 
 * How many distinct terms are in the sequence generated by a^(b) for 2 ≤ a ≤
 * 100 and 2 ≤ b ≤ 100?
 * 
 * 
 */
public class Game29_1 {
    public static void main(String[] args) {
        int bond = 100;
        int[] temp = new int[2];
        int result = 0;
        for (int i = 2; i <= bond; i++) {
            for (int j = 2; j <= bond; j++) {
                temp = convertToSimplestBasePower(i, j);
                if (!isDuplicated(temp)) {
                    result++;
                }
            }
        }
        System.out.println(result);
    }

    static HashMap<Integer, HashMap<Integer, Integer>> dictionary = new LinkedHashMap<Integer, HashMap<Integer, Integer>>();

    /**
     * 
     * judge whether duplicated, if not, add to dictionary.
     */
    public static boolean isDuplicated(int[] input) {
        int base = input[0];
        int power = input[1];
        HashMap<Integer, Integer> tempPowerMap;
        if (dictionary.containsKey(base)) {
            tempPowerMap = dictionary.get(base);
            if (tempPowerMap.containsKey(power)) {
                return true;
            } else {
                tempPowerMap.put(power, power);
                return false;
            }
        } else {
            tempPowerMap = new LinkedHashMap<Integer, Integer>();
            tempPowerMap.put(power, power);
            dictionary.put(base, tempPowerMap);
            return false;
        }
    }

    /**
     * convert to simplest type of power number For example: input (8,2). output
     * will be (2,6)
     * 
     */
    public static int[] convertToSimplestBasePower(int base, int power) {
        List<Integer> list = new LinkedList<Integer>();
        getCommonFactor(base, list);
        List<List<Integer>> goups = new ArrayList<List<Integer>>();
        int pre = 0;
        for (int temp : list) {
            if (temp != pre) {
                List<Integer> subGourp = new ArrayList<Integer>();
                subGourp.add(temp);
                pre = temp;
                goups.add(subGourp);
            } else {
                goups.get(goups.size() - 1).add(temp);
            }
        }
        int powerCount = 0;
        boolean hasPower = true;
        for (List<Integer> temp : goups) {
            int tempCount = temp.size();
            powerCount = powerCount == 0 ? tempCount : powerCount;
            if (tempCount != powerCount) {
                hasPower = false;
            }
        }
        if (hasPower) {
            base = 1;
            for (List<Integer> temp : goups) {
                base *= temp.get(0);
            }
            power *= goups.get(0).size();
        }
        int[] returnValue = new int[2];
        returnValue[0] = base;
        returnValue[1] = power;
        return returnValue;
    }

    /**
     * put smallest factors into given list object. For example : input 12, list
     * will be filled with [2,2,3]
     * 
     */
    public static void getCommonFactor(int number, List<Integer> list) {
        if (Prime.isPrime(number)) {
            list.add(number);
            return;
        }
        int loop = number / 2;
        for (int i = 2; i <= loop; i++) {
            if (number % i == 0) {
                list.add(i);
                getCommonFactor(number / i, list);
                break;
            }
        }
    }

}
